#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    unordered_map<string, int> mp;   // string -> id
    unordered_map<int, string> r_mp; // id -> string
    vector<vector<int>> edges;       // 邻接表
    

    void AddWord(string& word) {
        if (!mp.count(word)) {
            mp[word] = mp.size();
            r_mp[mp[word]] = word;
            edges.emplace_back();
        }
    }

    void AddVirtualEdge(string& word) {
        int id = mp[word];
        for (int i = 0; i < word.length(); i++) {
            char temp = word[i];
            word[i] = '*';
            AddWord(word);
            edges[mp[word]].emplace_back(id);
            edges[id].emplace_back(mp[word]);
            word[i] = temp;
        }
    }

    vector<vector<int>> bfsWithPath(unordered_set<int> &nodeSet, vector<bool> &visited, int endId) {
        unordered_set<int> nextNodes;
        for (const int &t: nodeSet) {
            if (t == endId) {
                vector<int> res;
                res.emplace_back(endId);
                vector<vector<int>> ans;
                ans.emplace_back(res);
                return ans;
            }

            for (int i = 0; i < edges[t].size(); i++) {
                if (!visited[edges[t][i]]) {
                    nextNodes.insert(edges[t][i]);
                    visited[edges[t][i]] = true;
                }
            }
        }
        vector<vector<int>> temp = bfsWithPath(nextNodes, visited, endId), ans;
        for (int i = 0; i < temp.size(); i++) {
            for (int j = 0; j < edges[temp[i][0]].size(); j++) {
                if (nodeSet.count(edges[temp[i][0]][j])) {
                    ans.emplace_back(temp[i]);
                    ans[ans.size() - 1].insert(ans[ans.size() - 1].begin(), edges[temp[i][0]][j]);
                }
            }
        }
        return ans;
    }

    bool is_valid(string& str) {
        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '*') return false;
        }
        return true;
    }


    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        // 建图
        AddWord(beginWord);
        for (int i = 0; i < wordList.size(); i++) {
            AddWord(wordList[i]);
        }
        if (!mp.count(endWord)) {
            return vector<vector<string>>();
        }
        AddVirtualEdge(beginWord);
        for (int i = 0; i < wordList.size(); i++) {
            AddVirtualEdge(wordList[i]);
        }

        // 宽搜
        int beginId = mp[beginWord], endId = mp[endWord];
        unordered_set<int> st;
        st.insert(beginId);
        vector<bool> visited(mp.size(), false);
        visited[beginId] = true;
        vector<vector<int>> ans_int = bfsWithPath(st, visited, endId);
        vector<vector<string>> ans(ans_int.size());
        for (int i = 0; i < ans_int.size(); i++) {
            for (int j = 0; j < ans_int[i].size(); j++) {
                if (is_valid(r_mp[ans_int[i][j]])) {
                    ans[i].push_back(r_mp[ans_int[i][j]]);
                }
            }
        }
        return ans;
      
    }
};

/**
 * 2023.4.14
*/